package leetcode.code524;

import java.util.List;
import java.util.PriorityQueue;

public class Solution extends Solution524 {

	@Override
	public String findLongestWord(String s, List<String> dictionary) {
		PriorityQueue<String> pq = new PriorityQueue<>((o1, o2) -> {
			if (o2.length() > o1.length()) {
				return 1;
			} else if (o2.length() == o1.length()) {
				return o1.compareTo(o2);
			} else
				return -1;
		});
		for (String dic : dictionary) {
			pq.add(dic);
		}
		while (!pq.isEmpty()) {
			String str = pq.poll();
			if (this.substring(str, s)) {
				return str;
			}
		}
		return "";
	}

	private boolean substring(String str, String s) {
		int p1 = 0;
		int p2 = 0;
		while (p1 < str.length() && p2 < s.length()) {
			if (str.charAt(p1) == s.charAt(p2)) {
				p1++;
				p2++;
			} else {
				p2++;
			}
		}
		return p1 == str.length() ? true : false;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
//		String a = "abc";
//		String b = "acd";
//		System.out.println(a.compareTo(b));
	}

}
